package first.forHuaWei.codeTop;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC679
 * @description:
 * @author: 荣燊
 * @create: 2021-09-13 10:48
 **/
public class LC679 {
    // 24点游戏
    public static void main(String[] args) {

    }

    static int target = 24;
    static double mistake = 1e-6;
    static int add = 0, multiply = 1; //加，乘
    static int subtract = 2, divide = 3; // 减，除

    // 总共的所有可能也就9216种
    public static boolean judgePoint24(int[] cards) {
        ArrayList<Double> doubles = new ArrayList<>();
        for (int num : cards) {
            doubles.add((double) num);
        }
        return solve(doubles);
    }

    public static boolean solve(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }
        // 最后遍历到数组中只有一个元素
        if (list.size() == 1) {
            return Math.abs(list.get(0)-target) < mistake; //在这个差值之外，我们认为其就是24
        }
        int size = list.size();
        // 随机获取该list集合中的第i位与第j位
        for (int i=0; i<size; i++) {
            for (int j=0; j<size; j++) {
                if (i != j) {
                    // 将除了该i位与j位的元素加入到集合中
                    ArrayList<Double> list1 = new ArrayList<>();
                    for (int k=0; k<size; k++) {
                        if (k != i && k != j) {
                            list1.add(list.get(k));
                        }
                    }
                    // 对于除去的两个数，加减乘除都使用下
                    for (int k=0; k<4; k++) {
                        // 乘法和加法不需要重复计算
                        if (i > j && k < 2) {
                            continue;
                        }
                        if (k == add) {
                            list1.add(list.get(i)+list.get(j));
                        }else if (k == multiply) {
                            list1.add(list.get(i)*list.get(j));
                        }else if (k == subtract) {
                            list1.add(list.get(i)-list.get(j));
                        } else if (k == divide) {
                            if (list.get(j) < mistake) {
                                continue;
                            } else {
                                list1.add(list.get(i)/list.get(j));
                            }
                        }
                        if (solve(list1)) {
                            return true;
                        }
                        list1.remove(list1.size()-1);
                    }
                }
            }
        }
        return false;
    }

}
